Search for: All records

Abstract Given graph$$G=(V,E)$$ $G=(V,E)$with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ $k\ge 2$, our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ $k=2$and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem. 

The numerical performance of algorithms can be studied using test sets or procedures that generate such problems. This paper proposes various methods for generating linear, semidefinite, and secondorder cone optimization problems. Specifically, we are interested in problem instances requiring a known optimal solution, a known optimal partition, a specific interior solution, or all these together. In the proposed problem generators, different characteristics of optimization problems, including dimension, size, condition number, degeneracy, optimal partition, and sparsity, can be chosen to facilitate comprehensive computational experiments. We also develop procedures to generate instances with a maximally complementary optimal solution with a predetermined optimal partition to generate challenging semidefinite and second-order cone optimization problems. Generated instances enable us to evaluate efficient interior-point methods for conic optimization problems. 

Various noise models have been developed in quantum computing study to describe the propagation and effect of the noise that is caused by imperfect implementation of hardware. Identifying parameters such as gate and readout error rates is critical to these models. We use a Bayesian inference approach to identify posterior distributions of these parameters such that they can be characterized more elaborately. By characterizing the device errors in this way, we can further improve the accuracy of quantum error mitigation. Experiments conducted on IBM’s quantum computing devices suggest that our approach provides better error mitigation performance than existing techniques used by the vendor. Also, our approach outperforms the standard Bayesian inference method in some scenarios. 

Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to ℓ1-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution. 

This paper revisits the parametric analysis of semidefinite optimization problems with respect to the perturbation of the objective function along a fixed direction. We review the notions of invariancy set, nonlinearity interval, and transition point of the optimal partition, and we investigate their characterizations. We show that the set of transition points is finite and the continuity of the optimal set mapping, on the basis of Painlevé–Kuratowski set convergence, might fail on a nonlinearity interval. Under a local nonsingularity condition, we then develop a methodology, stemming from numerical algebraic geometry, to efficiently compute nonlinearity intervals and transition points of the optimal partition. Finally, we support the theoretical results by applying our procedure to some numerical examples.